package main

import "fmt"

/*
连续子数组的最大和
输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
要求时间复杂度为O(n)。

示例1:
输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
*/

//动态规划
//用第i-1的数组的连续子数组的最大和与nums[i]比较 如果前者大 则用前者替换nums[i]
//后者大的话 就以nums[i]为新起点继续循环
/*
func maxSubArray(nums []int) int {
	max := nums[0]
	for i := 1; i < len(nums); i++ {
		if nums[i]+nums[i-1] > nums[i] {
			nums[i] += nums[i-1]
		}
		if nums[i] > max {
			max = nums[i]
		}
	}
	return max
}
*/

//自己想的动态规划
func maxSubArray(nums []int) int {
	max := nums[0] //全局最大值
	cur := nums[0] //临时的最大值
	for i := 1; i < len(nums); i++ {
		if cur+nums[i] > nums[i] {
			cur += nums[i]
		} else {
			cur = nums[i]
		}
	}
	if cur > max {
		max = cur
	}
	return max
}

func main() {
	nums := []int{-2, 1}
	fmt.Println(maxSubArray(nums))
}
